package datastructure.tree;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/26 10:14 下午
 */
public class RedBlackTree<Key extends Comparable<Key>, Value> {

    public void put(Key key,Value value){
        if (key==null){
            return;
        }
        if (value==null){
            delete(key);
            return;
        }
        root=put(root,key,value);
        root.color =BLACK;
    }

    private Node put(Node root, Key key, Value value) {
        if (root==null){
            return new Node(RED,key,value,1);
        }
        int result=key.compareTo(root.key);
        if(result<0){
            root.left=put(root.left,key,value);
        }else if (result>0){
            root.right=put(root.right,key,value);
        }else {
            root.value=value;
        }

        if (isRed(root.right) && !isRed(root.left)){
            root=rotateLeft(root);
        }
        if (isRed(root.left) && isRed(root.left.left)){
            root=rotateRight(root);
        }
        if (isRed(root.left) && isRed(root.right)){
            flipColors(root);
        }
        root.size=1+size(root.left)+size(root.right);
        return root;
    }

    private void flipColors(Node root) {
        root.color=!root.color;
        root.left.color=!root.left.color;
        root.right.color=!root.right.color;
    }

    private Node rotateRight(Node node) {
        Node left= node.left;
        node.left=left.right;
        left.right=node;

        left.color=node.color;
        node.color=RED;

        left.size=node.size;
        node.size=1+size(node.left)+size(node.right);
        return left;
    }

    private Node rotateLeft(Node node) {
        Node right = node.right;
        node.right=right.left;
        right.left=node;

        right.color=node.color;
        node.color=RED;

        right.size=node.size;
        node.size=1+size(node.left)+size(node.right);
        return right;
    }

    private int size(Node node) {
        return node==null?0:node.size;
    }

    private boolean isRed(Node node) {
        return node==null?false:node.color;
    }

    public void delMin(){
        if (root==null){
            return;
        }
        if (!isRed(root.left) && !isRed(root.right)){
            root.color=RED;
        }
        root=delMin(root);
        root.color=RED;
    }

    private Node delMin(Node root) {
        if (root.left==null){
            return null;
        }
        if (!isRed(root.left) && !isRed(root.left.left)){
            root=moveRedLeft(root);
        }
        root.left=delMin(root.left);
        return balance(root);
    }

    private Node balance(Node root) {
        if (isRed(root.right)){
            root=rotateLeft(root);
        }
        if (isRed(root.right)&&!isRed(root.left)){
            root=rotateLeft(root);
        }
        if (isRed(root.left) && isRed(root.left.left)){
            root=rotateRight(root);
        }
        if (isRed(root.left) && isRed(root.right)){
            flipColors(root);
        }
        root.size = size(root.left)+size(root.right)+1;
        return root;
    }

    private Node moveRedLeft(Node root) {
        flipColors(root);

        if (isRed(root.right.left)){
            root.right=rotateRight(root.right);
            root=rotateLeft(root);
            flipColors(root);
        }
        return root;
    }

    public Value get(Key key){
        if (key==null){
            return null;
        }
        return get(root,key);
    }
    private Value get(Node node, Key key) {
        while (node!=null){
            int result=key.compareTo(node.key);
            if (result<0){
                node=node.left;
            }else if (result>0){
                node=node.right;
            } else {
                return node.value;
            }
        }
        return null;
    }
    private void delete(Key key) {

    }


    private Node root;
    private static final boolean RED = true;
    private static final boolean BLACK = false;


    private class Node {
        Node left, right;
        boolean color;
        Key key;
        Value value;
        int size;

        public Node(boolean color, Key key, Value value, int size) {
            this.color = color;
            this.size = size;
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        RedBlackTree<String,Object> tree = new RedBlackTree<>();
       /* Random random=new Random();
        long start=System.currentTimeMillis();

        long end=System.currentTimeMillis();
        System.out.println("插入800W数据时间："+(end-start));*/
        tree.put("a",1);
        tree.put("i",5);
        tree.put("b",2);
        tree.put("c",3);
        tree.put("f",5);
        tree.put("d",4);
        tree.put("g",5);
        tree.put("j",5);
        tree.put("h",5);
        tree.put("h",5);
        tree.put("i",5);
        tree.put("k",5);
        tree.put("l",5);
        tree.put("m",5);
        tree.put("e",5);
        tree.delMin();
        int size = tree.size(tree.root);
        System.out.println(size);
        System.out.println(tree.get("a"));
        System.out.println(tree.get("c"));

    }
}
